package com.xiaoyu.binarySearch;

/**
 * @program: DS_and_A
 * @description: 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
 *
 * 输入：x = 2.00000, n = -2
 * 输出：0.25000
 * 解释：2^-2 = 1/2^2 = 1/4 = 0.25
 *
 * @author: YuWenYi
 * @create: 2021-05-05 19:12
 **/
/*    //暴力解法!,时间复杂度太高,不满足题意
      double res = 1;
        if (n == 0 || x == 1){
            return 1;
        }else if (n > 0){
            for (int i = 0; i < n; i++) {
                res *= x;
            }
        }else {
            x = 1/x;
            for (int i = 0; i < -n; i++) {
                res *= x;
            }
        }
        return res;*/
public class MyPow {

    public static double myPow(double x, int n) {
       long N = n; //必须要把n存入long中,不然Integer.MIN_VALUE这个值进行绝对值操作时候就会出现错误!
       return N > 0 ? quickMul(x,N) : 1.0/quickMul(x,-N);
    }
    //官方解法一,快速幂+递归
   /* public static double quickMul(double x, long N) {
        if (N == 0){
            return 1.0;
        }
        double y = quickMul(x,N/2); //当N小于2的时候,N/2就会等于0
        //如果N是奇数,则需要多乘一个x,例如 x^9 = x^4 * x^4 * x
        return (N & 1) == 1 ? y*y*x : y*y;
    }*/

    //官方解法二:快速幂+迭代
    //简单来说,就是将x^n次方分解为x^n1 * x^n2... n1+n2+... = n,而n1,n2又有下面的规律
    //x^77,这些指数 1，4，8和 64，恰好就对应了 77 的二进制表示 (1001101)中的每个 1！,因此有如下思路
    //当二进制中的某个位置上的数字为1时,才相乘!
    public static double quickMul(double x, long N) {
        double ans = 1.0;
        double x_mi = x;
        //遍历N的二进制数的所有位置,从右到左
        while (N > 0){
            //如果N是奇数,即N的二进制表示中的最低位是1
            if ((N & 1) == 1){
                ans = ans * x_mi;
            }
            //舍弃N的最低位,即N/2
            N = N >> 1; //N的二进制右移一位,代表着遍历少一个

            //每次N右移了一位,都需要将x的幂进行平方操作
            x_mi = x_mi * x_mi;
        }
        return ans;
    }

    public static void main(String[] args) {
        double pow = myPow(2,10);
        System.out.println("pow:"+pow);
    }
}
